package puzzle.projecteuler.p100;

import java.util.Arrays;

import astudy.util.AdvMath;

public class Problem070B {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		int m = 10000000;
		int[] phis = AdvMath.phis(m);
		int n = -1;
		for (int i = 2; i < phis.length; i ++) {
			if (check(i, phis[i])) {
				if (n == -1 || ((long)n*phis[i] > (long)i*phis[n])) {	//注意，这里为了避免溢出，需要转成long类型再比较
					n = i;
				}
			}
		}
		System.out.println(n);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}

	private static boolean check(int m, int n) {
		
		char[] a = String.valueOf(m).toCharArray();
		char[] b = String.valueOf(n).toCharArray();
		if (a.length != b.length) {
			return false;
		} else {
			Arrays.sort(a);
			Arrays.sort(b);
			for (int i = 0; i < a.length; i ++) {
				if (a[i] != b[i]) return false;
			}
			return true;
		}
	}
}
